package kyssion.leetcode.num1_50;


import java.util.ArrayList;

/**
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * <p>
 * 示例 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class code5_回文子串 {

    public static void main(String[] args) {
        System.out.println(new code5_回文子串().longestPalindrome3(""));
    }

    /**
     * 使用Manacher算法
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        char[] at = new char[s.length() * 2 + 1];
        int[] length = new int[s.length() * 2 + 1];
        for (int a = 0; a < s.length(); a++) {
            at[a * 2] = '#';
            at[2 * a + 1] = s.charAt(a);
        }
        at[at.length - 1] = '#';
        length[0] = 1;
        int maxRight = 0;
        int center = 0;
        int index = 0;
        for (int a = 0; a < at.length; a++) {
            if (a < maxRight) {
                length[a] = Math.min(maxRight - a, length[2 * center - a]);
            } else {
                length[a] = 1;
            }
            while (a - length[a] >= 0 && a + length[a] <= at.length - 1) {
                if (at[a - length[a]] == at[a + length[a]]) {
                    length[a]++;
                    continue;
                }
                break;
            }
            if (a + length[a] > maxRight) {
                center = a;
                maxRight = a + length[a];
            }
            index = length[index] < length[a] ? a : index;
        }
        return getString(index, length, at);
    }

    public String getString(int index, int[] length, char[] at) {
        ArrayList<Character> arrayList = new ArrayList<>();
        for (int start = index - length[index] + 1, end = index + length[index] - 1; start <= end; start++) {
            if (at[start] != '#') {
                arrayList.add(at[start]);
            }
        }
        char[] c = new char[arrayList.size()];
        for (int a = 0; a < arrayList.size(); a++) {
            c[a] = arrayList.get(a);
        }
        return new String(c);
    }

    /**
     * 我之前的奇葩写法,不知道为啥是对的
     *
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        char[] at = new char[s.length() * 2 + 1];
        int[] length = new int[s.length() * 2 + 1];
        for (int a = 0; a < s.length(); a++) {
            at[a * 2] = '#';
            at[2 * a + 1] = s.charAt(a);
        }
        at[at.length - 1] = '#';
        length[0] = 1;
        int nowIndex = 0;
        int index = 0;
        for (int a = 0; a < at.length; a++) {
            if (nowIndex + length[nowIndex] > a) {
                length[a] = Math.min(nowIndex + length[nowIndex] - a, length[2 * nowIndex - a]);
            } else {
                length[a] = 1;
            }
            while (a - length[a] >= 0 && a + length[a] <= at.length - 1) {
                if (at[a - length[a]] == at[a + length[a]]) {
                    length[a]++;
                    continue;
                }
                break;
            }
            if (a + length[a] > nowIndex + length[nowIndex]) {
                nowIndex = a;
            }
            index = length[index] < length[a] ? a : index;
        }
        return getString(index, length, at);
    }

    /**
     * 从中间向两边遍历查询查找
     *
     * @param s
     * @return
     */
    public String longestPalindrome3(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}
